#coding=utf-8

from numpy import*
import time
#简单数据
def loadSimpDat():
    #书中数据
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    # #例子数据
    # simpDat=[[1,2,5],  #第1
    #          [2,4],
    #          [2,3],
    #          [1,2,4],
    #          [1,3],
    #          [2,3],
    #          [1,3],
    #          [1,2,3,5],
    #          [1,2,3]]  #第9

    return simpDat


#把原始数据处理成字典形式
def createInitSet(dataSet):
    retDict={}
    for transaction in dataSet:
        retDict[frozenset(transaction)]=1
    return retDict

#构建FP树的数据结构
class treeNode:
    def __init__(self,nameValue, numOccur, parentNode):
        self.name = nameValue   #结点名称
        self.count = numOccur #结点出现次数
        self.nodeLink = None  #链接相似元素项（横向找）
        self.parent = parentNode  #父结点（由上往下找）
        #字典类型，存孩子名称及计数
        self.children = {} #子结点（由下往上找）
    #增加次数
    def inc(self, numOccur):
        self.count += numOccur
    #显示FP树结构
    def disp(self, ind=1):
        #为了显示有序
        #当前结点显示的最前面有ind个空格，其子结点输出空格数ind+1
        print '  '*ind, self.name, ' ', self.count
        for child in self.children.values():
            child.disp(ind+1)

#创建FP树
#dataSet:字典类型，一条记录及对应次数
#minSup:最小支持度数
def createTree(dataSet, minSup=1):
	#创建头指针表，存储元素及出现频数<key,value>
    headerTable = {}
    #扫描两次数据集
    #***第1次扫描数据集,创建头指针表
	#1遍历扫描数据集统计元素的频数
    for trans in dataSet: #同for trans in dataSet.keys():
        for item in trans:
			#统计元素项出现的次数：dict.get(key,default=None)返回指定key计数
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    #2删除小于最小支持度数的项
    for k in headerTable.keys():
        if headerTable[k] < minSup: #移除小于支持度的项元素
            del(headerTable[k])

    #3.去重得到频繁1项集
    freqItemSet = set(headerTable.keys())#把字典的key取出来
    # print 'freqItemSet: ',freqItemSet

    #若没有频繁项集，则返回
    if len(freqItemSet) == 0: return None, None
    #在头指针表中，添加指向项的指针
    for k in headerTable:
        #存放指向相似元素项的指针None
        headerTable[k] = [headerTable[k], None]
    #print 'headerTable: ',headerTable
    #创建根结点：名称Null Set,出现次数为1
    retTree = treeNode('Null Set', 1, None)

    #***第2次扫描数据集,创建头指针表
    #遍历每条记录及次数
    for tranSet, count in dataSet.items():
        #对每项商品，记录次数
        localD = {} #key:商品名称，#value:出现次数
        for item in tranSet:  #遍历每项商品
            if item in freqItemSet:#若该商品在频繁项集中
                #出现物品出现的次数
                localD[item] = headerTable[item][0]

        if len(localD) > 0:
            #每条记录下的元素项次数排序
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
            #利用排序过滤后的交易记录，插入到树中，更新FP树
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable

#items:排好序的某条物品项; inTree:构建的FP-tree;
#headerTable:头指针表;count:计数为1
def updateTree(items, inTree, headerTable, count):
    #如果排好序的记录的第一个项已在树inTree中,计数加1
    if items[0] in inTree.children:
        inTree.children[items[0]].inc(count)
    else:
        #没有这个元素，创建新结点treeNode，作为子节点添加到树中
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        #更新该项的指针链表
        if headerTable[items[0]][1] == None:
            #头指针未指向任何相似元素项，则指向该元素项
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            #头指针已经指向相似元素项，那么更新头指针表，连接该元素项
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    #对剩下的元素项依次插入到树中，不断调用自身
    #每次调用时去掉items的第一个元素项
    if len(items)>1:
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)

#更新相似元素项的链表指向
def updateHeader(nodeToTest, targetNode):
    #从链表头开始找尾（直到nodeToTest.nodeLink为空）
    while(nodeToTest.nodeLink != None):
        nodeToTest = nodeToTest.nodeLink
    #将链表尾部指向新的相似元素项
    nodeToTest.nodeLink = targetNode

#为给定元素项找前缀路径（条件模式基）
#通过访问树中所有包含给定元素项的结点完成
#输入：basePat是要挖掘的元素项名称
#treeNode为要挖掘元素项结点
#通过headerTable[basePat][1]获取
def findPrefixPath(basePat, treeNode):
    #存放条件模式基，即包含元素项basePat的前缀路径
    #<key,value>中key：前缀路径，value:前缀路径计数
    condPats={} #存前缀路径及计数
    #从要挖掘元素项结点开始往上找，直到找到根节点
    while treeNode != None:
        prefixPath=[] #存前缀路径
        #从要挖掘的元素项结点往上找直到根节点
        #记下路径（该元素项和根节点之间的元素项，包含该元素项）
        ascendTree(treeNode, prefixPath)
        #当路径中的元素项个数大于1
        if len(prefixPath)>1:
            #去掉要挖掘的元素项自身，得到前路路径prefixPath[1:]
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        #继续查找下一个相似元素的前缀路径
        treeNode = treeNode.nodeLink
    #返回该元素的所有条件模式基(前缀路径)
    return condPats

#向上搜索,找当前结点leafNode的路径
#存于prefixPath中(包含当前结点leafNode，不包含根节点)
def ascendTree(leafNode, prefixPath):
    #向上找，如果当前结点的父亲结点不为空，记下该结点
    #继续递归向上找
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

#***挖掘条件树，查找频繁项集
#freItemList空列表[],保存生成的频繁项集
#preFix空集合set()存当前前缀
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    #对头指针表中的元素按照出现次数从小到大排序
    bigL=[v[0] for v in sorted(headerTable.items(), key=lambda p:p[1])]
    #从满足最小支持度的头指针表的最小元素项开始遍历，挖掘前缀basePat的频繁项集
    for basePat in bigL:
        #上一轮的preFix前缀元素项
        newFreqSet = preFix.copy()
        #当前的前缀元素项
        newFreqSet.add(basePat)
        #所有的频繁项集
        freqItemList.append(newFreqSet)
        #找元素项basePat的前缀路径
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        #print 'condPattBases :',basePat, condPattBases
        #条件模式基构建条件FP树
        myCondTree, myHead = createTree(condPattBases, minSup)
        #print 'head from conditional tree: ', myHead
        #若条件FP树中有元素，可以再次递归调用条件FP树
        if myHead != None: #3. mine cond. FP-tree
            print 'conditional tree for: ', newFreqSet
            myCondTree.disp(1)
            #
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

def fpGrowth(dataSet, minSup=3):
    #初始化数据集
    initSet = createInitSet(dataSet)
    #创建FP树
    myFPtree, myHeaderTable = createTree(initSet, minSup)
    #保存频繁项集列表
    freqItems=[]
    #递归构建条件FP树，查找频繁项集
    mineTree(myFPtree, myHeaderTable, minSup, set([]), freqItems)
    return freqItems

if __name__=='__main__':
    simpDat = loadSimpDat()
    dataSet = createInitSet(simpDat)

    myFPtree, myHeaderTable = createTree(dataSet, minSup=3)
    myFPtree.disp()

    # #找频繁项集：
    # condPats=findPrefixPath('r',myHeaderTable['r'][1])
    # print 'condPats=',condPats

    #挖掘条件树,找频繁项集
    freqItems=[]
    mineTree(myFPtree, myHeaderTable, 3, set([]), freqItems)
    print 'freqItems=', freqItems
